/*
	test4
*/

/*
	给出两个非空的链表用来表示两个非负的整数。
	其中，它们各自的位数是按照逆序的方式存储的，
	并且它们的每个节点只能存储一位数字。
	如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
	您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
	例如：链表l1=(2 -> 4 -> 3),l2=(5 -> 6 -> 4),
	返回链表l3=7 -> 0 -> 8,因为342 + 465 = 807
*/
LinkList* addTwoNumber(LinkList *l1,*l2)
{
	int i=0,t,x,y;
	LinkList *L,*p,*q,*r,*m;
	L = (LinkList *)malloc(sizeof(LinkList));
	L->next = NULL;
	r = L;
	p = l1;
	q = l2;//p是l1的工作指针 q是l2的工作指针

	while(p||q)
	{
		x=(p!=NULL)?p->data:0;
		y=(q!=NULL)?q->data:0;//
		t = x+y+i;//i表示从下一层仅为上来的数

		if(t>=10)
		{
			t=t%10;
			i=1;
		}
		else
			i=0;

		//构造新节点m,将加上的数据存入m并链入L
		m = (LinkList *)malloc(sizeof(LinkList));
		m->data=t;
		r->next=m;
		r=m;
		if(p) p=p->next;
		if(q) q=q->next;
	}

	if(i==1)
	{
		m = (LinkList *)malloc(sizeof(LinkList));
		m->data=1;
		r->next=m;
		r=m;
	}

	r->next = NULL;
	L=L->next;

	return L;
}

/*
	给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，
	使得剩下的数字最小。
	例如 ：当num = "1432219", k = 3，
	我们得到的最小的数为1219，
	即移除掉num的三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
	当num = "10200", k = 1，移掉首位的 1 剩下的数字为 200. 
	注意输出不能有任何前导零。
	当num = "10", k = 2，从原数字移除所有的数字，剩余为空就是0。

	解题思路(贪心)
	从高位开始走，如果下一个数字比当前数字小，
	且要删除的数字次数没用完，则删除当前位置的数字，
	且继续向前比较，这样总能得到一个较小的序列
*/

char* removeK(char* num,int k)
{
	if(k<=0)
		return num;

	if(strlen(num) == 0 || k>= num.length())
		return "0";
	int length = strlen(num)
	int digits = length -k;//输出的字符串长度
	char stack[length];//模拟栈
	int top = 0;//记录栈顶元素的下一个位置

	for(int i = 0; i<length;i++)//遍历所有元素
	{
		char c = num[i];
		while(top>0 && stack[top-1]>c && k>0)
		{//如果当前元素比栈顶元素小,则出栈
			top--;
			k--;
		}

		stack[top++]=c;
	}

	//从头开始查找头不为0的位置
	int idx=0;
	while(idx < digits && stack[idx] == '0')
	{
		idx++;
	}

	if(idx == digits)
		return "0";
	else
	{
		char *m = (char *)malloc(sizeof(char)*(digits-idx));

		for(int i = 0; i<digit-idx; i++)
		{
			m[i] = stack[idx];
		}

		return m;
	}
}

/*
	用两个栈来实现一个队列，完成队列的Push和Pop操作。
	队列中的元素为int类型。可以使用栈的基本操作,push,pop,等。
*/
typedef struct queue
{
	Stack s1;
	Stack s2;
}

int queuePush(queue *S, int x)
{
	if(!overflowStack(S.s1))
		push(S.s1,x);
		return 1;
	else
		return 0;
}

void queuePop(queue *S, int &x)
{
	int e;
	if(emptyStack(S.s1))
		return 0;
	else
	{
		while(!emptyStack(S.s1))
		{
			pop(S.s1,e);
			push(S.s2.e);
		}

		pop(S.s2,x);

		while(!emptyStack(S.s2))
		{
			pop(S.s2,e);
			push(S.s1.e);
		}
	}
}

/*
	给定一个二叉树（具有根结点 root），
	一个目标结点 target ，和一个整数值 K 。
	返回到目标结点 target 距离为 K 的所有结点的值的列表。 
	答案可以以任何顺序返回。
*/
void gen(Bitree *root, int k, int *a, int *n)
{
	if(root ==NULL ||k<0)
		return;
	if(k==0)
	{
		a[]
	}
}

/*
	输入一个整数数组，判断该数组是不是某二叉排序树的后序遍历的结果
	假设输入的数组的任意两个数字都互不相同
*/
bool recoverTree(int *A,int f, int r)
{
	if(f==r) return true;

	int i;
	for(i = f;i<r;i++)
	{
		if(A[i]>A[r])
			break;
	}

	bool left = recoverTree(A,f,i-1);
	bool right = recoverTree(A,i,r-1);

	for(;i<r;i++)
	{
		if(A[i]<A[r])
			return false;
	}

	return left && right;
}

/*
	返回数组的逆序对
*/
int mergesort(int *A, int n)
{
	int tmp[n];
	int count = mergepass(A,0,n-1,tmp);
	free(tmp);
	return count;
}

int mergepass(int *A, int p, int r, int *tmp)
{
	int count1 = 0,count2 = 0,count3 = 0;
	if(p<r)
	{
		int mid = (p+r)/2;
		count1 = mergepass(A,p,mid,tmp);
		count2 = mergepass(A,mid+1,r,tmp);
		count3 = merge(A,p,mid,r,tmp);		
	}
	return count1 + count2 + count3;
}

int merge(int *A, int p, int mid,int r, int *tmp)
{
	int i = p; int j = mid+1;
	int n = mid; int m = r;
	int k  = 0; int count= 0;

	while(i<=n &&j<=m)
	{
		if(A[i]<=A[j])
			tmp[k++] = A[i++];
		else
		{
			tmp[k++] = A[j++];
			count = n-i+1;
			//左边的大于右边的,左边后面的个数就是该段序列所有的逆序对
		}
	}

	while(i<=n)
		tmp[k++] = A[i++];
	while(j<=m)
		tmp[k++] = A[j++];
	return count;
}

/*
	编辑距离，又称Levenshtein距离（也叫做Edit Distance),
	是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。
	许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，
	删除一个字符

	递归式
	min(i,j) = 0 lev(i,j)= max(i,j);

	A[i] = B[j]时,
	lev(i,j) = lev(i-1,j-1)
	比如xxcz 和 xyz = xxc和 xy
	
	A[i] != B[j]时,
		lev(i,j) = lev(i-1,j)+1  ,删除A[i]
		xxc 和 xyz = xx和 xyz +1

		lev(i,j) = lev(i,j-1)+1  ,A后插入B[j]
		xxc 和 xyz = xxcz 和 xyz + 1

		lev(i,j) = lev(i-1,j-1)+1  ,A[i]替换B[j]
		xxc 和 xyz = xxz和 xyz+1
*/
void Levenshtein(int **L, char *A ,char *B, int n, int m)
{
	for(int i = 0;i<n;i++)
	{
		L[i][0] = i;
	}
	for(int i = 0;i<m;i++)
	{
		L[0][i] = i;
	}

	for(int i = 1;i<n;i++)
	{
		for(int j = 1;j<m;j++)
		{
			if(A[i] = B[j])
				L[i][j] = L[i-1][j-1];
			else
			{
				L[i][j] = max(L[i-1][j],L[i][j-1,L[i-1][j-1]])+1;
			}
		}
	}

	return L[i-1][j-1];
}

/*
	八皇后问题
*/
int queen[8],count = 0;
int isok(int row)
{
	for(int i = 0;i<row;i++)
	{
		if(queue[i] == queue[row] || row-i==queue[row]-queue[i] || row-i==queue[i]-queue[row])
		{
			return false;
		}
	}
	return true
}

void que(int row)//初始位1
{
	if(row == 8)
		count++;
		return;

	for(int i = 1;i<=8;i++)
	{
		queue[row] = i;
		if(isok(row))
			que(row+1);
	}
}


/*
	test3
*/

/*
	设有两个无头结点的单链表,头指针分别为ha,hb,
	链中有数据域data,链域next,两链表的数据都按递增序存放,
	现要求将hb表归到ha表中,且归并后ha仍递增序,
	归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,
	hb的链表在算法中不允许破坏
*/
LinkList Union(LinkList ha,hb)
{//ha和hb是两个无头结点的数据域值递增有序的单链表，
 //本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表
	LinkList la,pa,pb,pre;
	la = (LinkList)malloc(sizeof(LinkList));
	la -> next = ha;//临时头结点f方便操作
	pa = ha; pb = hb; pre = la;
	while(pa!=NULL && pb!=NULL)
	{
		if(pa->data<pb->data)//处理ha
		{
			pre->next = pa;
			pre = pa;
			pa = pa->next;
		}
		else if(pa->data>pb->data)
		{
			r = (LinkList)malloc(sizeof(LinkList));
			r->data = pb->data;
			pre ->next = r;
			pre = r;
			pb = pb->next;
		}
		else
		{//处理相等的结点
			pb = pb->next;
		}
	}

	if(pa!=NULL) pre->next = pa;
	else pre ->next = pb;
	free(la);
}

/*
	写出在二叉排序树中删除一个结点的算法，
	使删除后仍为二叉排序树。设删除结点由指针p所指，
	其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。
	写出c语言代码
*/

/*
void delect(BiTree f)
{
	BiTree p = f->rchild, r;
	if(p->lchild && p->rchild)
	{
		r = p->lchild;
		f = p;
		while(r)
		{
			f = r;
			r = r->rchild;
		}

		p = r;
	}

	if(p->lchild)
	{
		r = p->lchild;
		f->rchild = r;
	}
}
*/

/*

*/
typedef struct node
{  
	float value;//存数值
	char optr;  //只取‘+’， ‘-’， ‘*’，‘/’
	struct node *lchild，*rchild ;
}BiNode,*BiTree;

float PostEval(BiTree bt)   // 以后序遍历算法求以二叉树表示的算术表达式的值
{
	float lv,rv;
	if(bt=NULL) return 0;
	if(bt!=NULL)
	{
		lv=PostEval(bt->lchild); // 求左子树表示的子表达式的值
		rv=PostEval(bt->rchild); // 求右子树表示的子表达式的值
		switch(bt->optr)
		{
			case ‘+’: bt->value=lv+rv; break;
			case ‘-’: bt->value=lv-rv;break;
			case ‘*’: bt->value=lv*rv;break;
			case ‘/’: bt->value=lv/rv;break;
		} 
	    return(bt->value);
	} 
}


/*
	设M是一个n行n列的0-1矩阵，每行的1都排在0的前面．
	设计一个最坏情况下O(nlogn)时间的算法找到M中含有1最多的行，
	说明算法的设计思想，估计最坏情况下的时间复杂度
*/

/*
	最优三角剖分
	t[i][j] 为凸多边形的V[i-1][j]的最有三角剖分,
			并且该部分包含三角形V(v-1,k,j)的权值
			以及子凸多边形V[i-1][k]和V[k][j]的权值
	t[i][j] = 0  i = j
	          min{t[i][k] + t[k+1][j] + w(i-1,k,j)}
*/
void minweightTriang(int n, int **t, int **s)
{
	for(int i  = 0;i<=n; i++)
	{
		t[i][i] = 0;
	}

	for(int r = 2; r<=n; r++)
	{//当前链长,也就是子规模，r=2表示有三个点
		for(int i = 1; i<=n-r+1; i++)
		{
			int j = i+r-1;//i为计算的前边界，当r为2时表示有三个点,j表示后边界
			t[i][j] = t[i+1][j] + w(i-1,i,j);//选择以i点划分点
			s[i][j] = i;

			for(int k = i+1;k<j; k++)
			{
				int tmp = t[i][k] + t[k+1][j] + w(i-1,k,j);
				if(tmp<t[i][j])
				{
					t[i][j] = tmp;
					s[i][j] = k;
				}
			}
		}
	}
}

/*
	硬币找零
*/
void greedMoney(int *v, int m, int n,int *s)
{//v[]:存放可供找零的面值,降序排列
 //m:  v数组长度
 //n   需要兑换的零钱
	int i;
	for(i = 0;i<k;i++)
	{
		while(n>=v[i])
			s[i]++;
			n =-v[i];
	}
}